Bem-vindo à Lição 3 de Conceitos de Inteligência Artificial (PolyU COMP5511). Nesta sessão, fazemos a transição da busca de caminhos de agente único para a Busca Adversarial, em que os agentes operam em ambientes multiagente competitivos. Apresentamos também os Problemas de Satisfação de Restrições (CSPs), um paradigma em que o objetivo é encontrar um estado que satisfaça um conjunto específico de restrições, em vez de um caminho.
Conceitos Fundamentais
- Busca Adversarial: Foca em algoritmos como Minimax e Poda Alfa-Beta para tomar decisões racionais contra um oponente inteligente.
- Busca em Árvore Monte Carlo (MCTS): Explora a tomada de decisão probabilística, servindo como base para IAs modernas de jogos como AlphaGo.
- Satisfação de Restrições: Modela problemas usando Variáveis, Domínios e Restrições, resolvidos por meio de Backtracking e Busca Local.
Análise de Complexidade
Em contextos adversariais, a complexidade do espaço de busca é frequentemente definida pelo fator de ramificação do jogo
Aviso de Mudança de Paradigma
Ao contrário da busca padrão (ex.: A* ou BFS), em que o ambiente é estático, a Busca Adversarial presume que o ambiente (o oponente) tenta ativamente minimizar o seu sucesso. Em CSPs, a ordem das ações importa menos do que a validade da atribuição final.
Pseudocódigo Conceitual: Tipos de Agentes
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).